package class14;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * <a href="https://leetcode.cn/problems/IPO/">502. IPO</a>
 * <p>
 * 假设 力扣（LeetCode）即将开始 IPO 。为了以更高的价格将股票卖给风险投资公司，力扣 希望在 IPO 之前开展一些项目以增加其资本。
 * 由于资源有限，它只能在 IPO 之前完成最多 k 个不同的项目。帮助 力扣 设计完成最多 k 个不同项目后得到最大总资本的方式。
 * 给你 n 个项目。对于每个项目 i ，它都有一个纯利润 profits[i] ，和启动该项目需要的最小资本 capital[i] 。
 * 最初，你的资本为 w 。当你完成一个项目时，你将获得纯利润，且利润将被添加到你的总资本中。
 * 总而言之，从给定项目中选择 最多 k 个不同项目的列表，以 最大化最终资本 ，并输出最终可获得的最多资本。
 * 答案保证在 32 位有符号整数范围内。
 */
public class Code04_IPO {

    /**
     * 找到最大化资本
     *
     * @param k       项目数量
     * @param w       初始资金
     * @param profits 纯利润
     * @param capital 启动该项目需要的最小资本
     * @return 最大化资本
     */
    public static int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        // 思路：利用一个小根堆存入启动项目最小资本，利用一个大根堆存入利润
        PriorityQueue<ProCap> minCap = new PriorityQueue<>(Comparator.comparingInt(o -> o.c));
        PriorityQueue<ProCap> maxPro = new PriorityQueue<>((o1, o2) -> (o2.p - o1.p));
        // 将启动资本与利润封装，放入小根堆中
        for (int i = 0; i < profits.length; ++i) {
            minCap.add(new ProCap(profits[i], capital[i]));
        }
        // 开始获取k个项目数量能拿到的最大资本
        while (k-- > 0) {
            // 先从minCap中拿出初始资金w能选的项目，并放入maxPro中
            while (!minCap.isEmpty() && minCap.peek().c <= w) {
                maxPro.add(minCap.poll());
            }
            // 如果说maxPro为空，说明w不足以买下任何的项目，直接返回w
            if (maxPro.isEmpty()) {
                return w;
            }
            // 开始抛出maxPro中最大利润的那个项目，累加w
            w += maxPro.poll().p;
        }
        return w;
    }

    // 将 profits 与 capital 封装起来，方便操作
    public static class ProCap {
        public int p, c;

        public ProCap(int p, int c) {
            this.p = p;
            this.c = c;
        }
    }

    public static void main(String[] args) {
        System.out.println(findMaximizedCapital(3, 0, new int[]{1, 2, 3}, new int[]{0, 1, 2}));
    }

}